package com.LeeCode;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * 找到字符串中所有字母异位词
 */

public class Code438 {
    public static void main(String[] args) {

        String s = "cbaebabacd";
        String p = "abc";
        System.out.println(new Code438().findAnagrams2(s, p));

    }

    public List<Integer> findAnagrams(String s, String p) {
        int len = p.length();
        char[] array = p.toCharArray();
        Arrays.sort(array);
        String key = new String(array);

        List<Integer> res = new ArrayList<>();

        for (int i = 0; i <= s.length() - len; i++) {
            String sub = s.substring(i, i + len);
            char[] subArray = sub.toCharArray();
            Arrays.sort(subArray);
            String tmp = new String(subArray);
            if (tmp.equals(key)) {
                res.add(i);
            }
        }
        return res;
    }

    public List<Integer> findAnagrams1(String s, String p) {
        List<Integer> res = new ArrayList<>();
        HashMap<Character, Integer> target = new HashMap<>();
        HashMap<Character, Integer> current = new HashMap<>();

        for (char c : p.toCharArray()) {
            target.put(c, target.getOrDefault(c, 0) + 1);
        }
        int diff = target.size(), window = p.length();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (target.containsKey(c)) {
                current.put(c, current.getOrDefault(c, 0) + 1);
                if (current.get(c).equals(target.get(c))) {
                    diff--;
                } else if (current.get(c) == target.get(c) + 1) {
                    diff++;
                }
            }

            if (i < window - 1) {
                continue;
            }

            int pos = i - window + 1;
            if (diff == 0) {
                res.add(pos);
            }

            c = s.charAt(pos);
            if (target.containsKey(c)) {
                current.put(c, current.getOrDefault(c, 0) - 1);
                if (current.get(c).equals(target.get(c))) {
                    diff--;
                } else if (current.get(c) == target.get(c) - 1) {
                    diff++;
                }
            }

        }
        return res;
    }

    public List<Integer> findAnagrams2(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int[] target = new int[26], cnt = new int[26];
        int diff = 0, window = p.length();
        for (char c : p.toCharArray()) {
            target[c - 'a']++;
            if (target[c - 'a'] == 1) diff++;
        }
        char[] chars = s.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            // 入
            cnt[chars[i] - 'a']++;
            if (cnt[chars[i] - 'a'] == target[chars[i] - 'a'])
                diff--;
            else if (cnt[chars[i] - 'a'] == target[chars[i] - 'a'] + 1)
                diff++;

            if (i < window - 1)
                continue;

            // 更新
            int pos = i - window + 1;
            if (diff == 0) {
                res.add(pos);
            }

            // 出
            cnt[chars[pos] - 'a']--;
            if (cnt[chars[pos] - 'a'] == target[chars[pos] - 'a'])
                diff--;
            else if (cnt[chars[pos] - 'a'] == target[chars[pos] - 'a'] - 1)
                diff++;

        }
        return res;
    }
}
